package com.sourcetrip.raw.adt;

import com.sourcetrip.raw.adt.abs.MyAbstractBinarySearchTree;
import com.sourcetrip.raw.model.MyBinaryNode;

import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/24
 * @description: 这个版本跟 第一个版本有所区别
 * 1.add();
 * 2.
 */
public class MyBinarySearchTree2<E extends Comparable> extends MyAbstractBinarySearchTree<E> {

	//private MyBinaryNode<E> root;

	@Override
	public void clear() {

	}

	/**
	 * 【前一个版本假设不会有相等的情况；
	 * 这个版本会考虑这种情况：
	 * -1-直接return;（√）
	 * -2-覆盖旧值
	 * 1.找到父节点；（这个必须得用循环！否则 O(n)=k^n !，经过测试，发现很容器就栈溢出！）
	 * 2.
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		//1.找到父节点
		//根节点的 父节点就是 null
		MyBinaryNode<E> pNode = null;
		//最后 cur 指向该放的位置，本质是 null
		MyBinaryNode<E> cur = this.root;
		//用循环，而不是递归！避免出现栈溢出！
		while (cur != null) {
			//修改父节点
			pNode = cur;
			if (cur.getElement().compareTo(element) > 0) {
				cur = cur.getLeft();
			} else if (cur.getElement().compareTo(element) < 0) {
				cur = cur.getRight();
			} else {
				return;
			}
		}
		//如果 父节点为 null,插入根节点（其实感觉一开始就处理根节点的情况会比较清爽！）
		if (pNode == null) {
			this.root = new MyBinaryNode<>(element, null);
		} else {
			MyBinaryNode<E> node = new MyBinaryNode<>(element, pNode);
			if (pNode.getElement().compareTo(element) > 0) {
				pNode.setLeft(node);
			} else {
				pNode.setRight(node);
			}
		}
		size++;
	}

	@Override
	public void remove(E element) {

	}

	/**
	 * 跟 add 时类似，但是不需要 parent node
	 *
	 * @param element
	 * @return
	 */
	@Override
	public boolean contains(E element) {
		MyBinaryNode<E> cur = this.root;
		while (cur != null) {
			if (cur.getElement().compareTo(element) > 0) {
				cur = cur.getLeft();
			} else if (cur.getElement().compareTo(element) < 0) {
				cur = cur.getRight();
			} else {
				return true;
			}
		}
		return false;
	}

	/**
	 * 这里做一个 中序遍历的循环打印
	 * @return
	 */
	@Override
	public String toString() {
		//做完先序遍历后，再写中序遍历的循环打印，是真的简单！
		// 那么我通过以下步骤已经是行云流水：
		// 1.画一棵符合各种情况的树；
		// 2.自己去走完流程画出每一步指针的指向，用上栈，并且思考各种判断条件：eg.什么时候入栈；什么时候终止循环
		// 3.用伪代码实现一下；用伪代码验证一遍流程是否符合预期；
		// 4.用 java 实现一遍
		StringBuilder sb = new StringBuilder();
		sb.append("[");

		if (size == 0) {
			//直接返回
			return sb.append("]").toString();
		}

		//region	写算法必须得将整个流程都捋顺！再去写！
		//首先一个指针是很有必要的！//感觉最重要的是，完整地把握好流程，然后写好伪代码！
		//1.建立一个栈用于存放右子树还没处理的节点
		//里面的节点都是已经打印过了的
		Stack<MyBinaryNode<E>> waitRootRightDealingStack = new Stack<>();
		MyBinaryNode<E> cur = root;

		//对栈弹出的元素进行标记 - 如果是出栈的元素，置为 true，不走第一个逻辑
		boolean isEleVisited = false;

		//因为这三个因素，都会是 cur 的下一个指向！
		//(既然这里不为null ,那么我就必须要在迭代中保证 cur 不会指向一个空指针！)
		while (cur.getLeft() != null || cur.getRight() != null || !waitRootRightDealingStack.isEmpty()) {
			//根据 左-根-右 的规则，让 cur 指向下一个
			if (cur.getLeft() != null && !isEleVisited) {
				//让该节点入栈
				waitRootRightDealingStack.push(cur);
				//指向下一个
				cur = cur.getLeft();
				isEleVisited = false;
			} else if (cur.getRight() != null) {
				sb.append(cur.getElement().toString()).append(", ");
				cur = cur.getRight();
				isEleVisited = false;
			}else {
				if (waitRootRightDealingStack.isEmpty()){
					//此时已经出栈的元素 && 只有一个左节点
					break;
				}
				sb.append(cur.getElement().toString()).append(", ");
				//既然已经到这里，说明 cur.getLeft == null && cur.getRight==null && stack is not Empty
				// 还有一种可能：最后的一个出栈的元素，躲过了第一层逻辑！即 left ！= null && stack is empty
				//此时弹出栈顶元素，作为指向的下一个元素
				cur = waitRootRightDealingStack.pop();
				isEleVisited = true;
			}
		}
		//此时 cur 指向最后一个节点
		sb.append(cur.getElement().toString());

		//endregion
		sb.append("]");
		return sb.toString();
	}
}
